The present invention relates generally to digital communication schemes, and more particularly to improvements in packet switching networks and systems.
Distributed packet switching architectures have been used for many years, since the advent of the microprocessor, and are essentially multi-microprocessor based systems in which a specific subset of system functions is assigned to each processor. The processors are interconnected by a bus over which they communicate and exchange status and user information for further processing or transmission by other processors. The classical packet switching architecture is hierarchical, and is used by virtually every packet switch other than desktop concentrators/network access devices.
In the architecture of the system, user traffic handling functions are distributed over the microprocessors according to the International Standards Organization's (ISO's) seven-layer (level) open system interconnection (OSI) protocol model, in which packet switches and networks implement the first three and in some instances the fourth layer, while the remaining layers are implemented in subscriber devices, such as computers or other terminals. In the ISO/OSI model, the first layer in the packet switch is the physical layer, which converts packets to and from the transmission medium-specific signals of the link (which may be microwave, copper, fiber optic, satellite, and/or other transmission facility) for transmission and reception over the link. In essence, this is the level that moves 1's and 0's across a transmission line. Level 2 is the link layer, which is responsible for transmitting and receiving complete and error-free packets across a link for the network layer. This second level handles the framing of packets on a per-link (line) basis, and maintains responsibility for successful receipt and transmission of packets across the link.
The third level is the network switching layer (packet level/switch level), which manages the user connection path through the network and routes packets containing user information over the path by looking inside each packet and then finding the correct output line. A path consists of one or more switches (nodes) connected by transmission links. Level 3 operates not on a per line basis, but through an understanding of the entire system.
The fourth level is the transport layer, which is the end to end network protocol, typically performed by a packet assembler/disassembler (PAD). Level 4 functions are used within the network only when the subscribers to be connected to the network communicate using a protocol different from the network's level 3 protocol. Level 4 functions are present only at points of entry and exit of the network, and primarily provide end to end network control and protocol conversion to the level 3 protocol for network transport.
The ISO/OSI seven-layer model is a classification scheme, but with advances in technology it has tended to be confused in a marketing sense with the technology itself. That is, because the first layer is extremely fast and is performed principally in hardware, and the second layer is also very fast, and the third layer is somewhat slower and more complex, the view in many quarters has become that these lower layers should be associated with speed and layer 1 with the hardware itself. The higher the number of the layer, the more complex and time consuming are the functions. The advent of extremely complex and high performance silicon chip technology has blunted this view, to some extent, permitting implementation of higher layer functions completely with hardware. It would appear to become more difficult, then, to maintain a view that hardware is restricted to level 1. But with increased sophistication of the technology and greater implementation in high speed integrated circuitry hardware, creative marketing approaches have led to assertions that formerly higher level ISO/OSI functions are now being performed in a lower layer in the product being marketed. In reality, of course, the ISO/OSI protocol was not intended to refer to specific technology, but merely to classification of universally required functions of the decision making process of transmitting user data through a network, regardless of whether the routing itself is accomplished in hardware, or in software, or by hierarchical or other processes.
The hierarchical architecture consists of a single level 3 processor which is capable of supporting several, even many, level 2 processors, each of which in turn is capable of supporting several/many level 1 processors. Level 3 contains the intelligence for making the packet routing decision, i.e., a particular packet is associated with a particular call and came in on a particular line and therefore it must go out on a specific line. In the hierarchical architecture, if several different entities were permitted to be involved simultaneously in this decision-making process the conflicts could be catastrophic. One level 3 processor might, for example, command that a connection should be torn down (disconnected) because of excessive traffic on a link, while another commanded that the same connection remain set up. The existence of only one arbiter of connection management, and only one system administrator, each of which is a "common control element", has been deemed a principal advantage of the hierarchical architecture.
A popular hierarchical architecture, multi-microprocessor based packet switch is the Sprint International Communications Corporation (formerly Telenet Communications Corporation) TP 4900, shown in highly simplified block diagrammatic form in FIG. 1. The packet switch includes a plurality of components implemented in integrated circuit module, board or card form, typically housed in a structure referred to as a cage. The cards are the functional elements of the architecture, and are interconnected by bus systems. Cards are inserted into slots to mate with connectors in the cage, and the bus and other cabling traverse the rear of the cage for intra- and inter-cage communications. A mailbox scheme is employed to synchronize interprocessor communications. One of the cards, a shared storage unit (SSU) 10, constitutes a global memory and is connected to the central bus system (CBS) bus 11. A portion of the global memory is reserved for each microprocessor card, and is subdivided into outgoing and incoming messages. The master central processing unit (MCPU) card 13 is the system administrator dedicated to control of system level activities, including responsibility for moving and routing outgoing messages to the incoming mailbox of the microprocessor card identified by an address in the header of the respective message.
A switch CPU (SCPU) 14 is the level 3 processor in the packet switch architecture of FIG. 1 and, like each of MCPU 13 and SSU 10, is a common control element (to be discussed in more detail presently). A plurality of line processing modules (LPMs) 16-1 through 16-n provide level 2 processing, with up to forty LPM slots available in the TP4900 switch (limited, however, by actual configuration and traffic). Each LPM is capable of supporting up to four protocol conversion units (PCUs) 18 which are connected to various transmission lines and provide level 1 processing for up to thirty-two physical transmission links.
The multi-microprocessor based architecture of the packet switch of FIG. 1 is a hierarchical distribution of functions as illustrated in FIG. 2. At the bottom of the hierarchy or pyramid are the level 1 PCU cards, with several supported by a single LPM level 2 card. At the top of the hierarchy are the common control elements (SSU 10, MCPU 13 and SCPU 14, in this example), so called because they are common to all traffic and the failure of any one of them will cause the entire packet switch to fail. In contrast, the failure of any of the other cards in the switch of FIG. 1 would cause only a loss of traffic passing through that card. Here, the SCPU performs all connection management, and the MCPU is the system administrator. The SSU, as noted earlier herein, is a memory board shared storage unit.
System configuration flexibility is achieved in this architecture by adding more processors which support the required layer, such as by adding level 1 (PCU) cards when more transmission lines are configured, and a level 2 (LPM) card if the current level 2 cards are configured to maximum capacity. Growth potential is restricted, however, depending on traffic types and configurations required. This restriction exists at least because of the following four factors, which are not necessarily listed in order of importance. First, the amount of memory available on the global memory card limits the number of mailboxes, routing information, and other control information that can be stored to describe a configuration. Second, the global memory speed limits the number of processors that can effectively access their mailboxes under sustained traffic loads. Third, the level 3 processor used for switching packets from an input level 2 processor to an output level 2 processor is capable of supporting only a finite number of line processors, and as explained previously, it is not possible to have more than one level 3 processor for this task in a hierarchical architecture. Fourth, the bus length and speed create further limitations, but always secondary to those mentioned above. It is noteworthy that all of these restrictions are directly or indirectly associated with a common logic element.
The third layer of the ISO/OSI, the switching level, is of particular interest in the present invention The first and second layers either receive a packet or are given a packet to transmit, without being required to know its origin or destination. In contrast, the third layer is an intelligent layer that recognizes the received packet, associates it with a particular connection, a particular source and a particular destination, to perform call set up and routing.
Another, less frequently encountered architecture may be characterized as "multiple switches in a box", or, more simply herein, as MSB. The MSB architecture actually uses many small hierarchical switches inside one "skin", or cage. It effectively puts all of the ISO/OSI level 1, level 2, and level 3 functions on each card, so that each acts as an autonomous, self-contained system, but located in the same "box", device or environment with the others. The switches are co-located and connected by a bus or by transmission lines. If the switches are in sufficiently close proximity, the transmission line may be an RS232 cable; whereas if they are separated by a vast distance the transmission line may be a toll line (fiber optic, microwave, or other) and a pair of modems. The MSB architecture is advantageous, for example, where a small desktop system is desired to have a larger system capability (expandability); but is disadvantageous because of its lower efficiency in network management and traffic handling operations.
By substituting a bus, a shared medium, for RS232 cabling in the MSB system, internal transmission speed is increased (megabits per second versus kilobits per second), and spaghetti-like cabling is eliminated. Despite some advantages over the strict hierarchical architecture, the MSB architecture only optimizes level 1, leaving level 3, and sometimes level 2, intact. Each card is now a separate switch and, in a network, if one fails, the other switches and the network control center ultimately determine where the failure occurred and how to circumvent it. The MSB system is neither as fast nor as efficient in these respects as the hierarchical architecture, which uses a separate system administration card--the MCPU in the aforementioned TP4900 packet switch--responsible for, among other things, monitoring the entire system and immediately identifying the location of a failure, followed by switchover from the failed card to a backup card.
The MSB architecture is a flat architecture, not hierarchical. If any card fails, the reaction and response is the same as if a node were lost in a network. In that circumstance, failure of the entire MSB device/switch is avoided because each card contains the intelligence to route around the problem. Within the switch, if enough redundant lines have been configured, the loss of one card will not adversely impact the remaining cards, except for the traffic that was passing through the failed card. One reason for referring to the MSB architecture as a flat architecture is that every element (i.e., switch comprising a card or group of cards acting as a single module) is capable of performing every function, in contrast to the element specialization of hierarchical architecture where, if one element fails, none other (apart from a backup) can perform its function In addition to that inefficiency, each common control element of the hierarchical architecture can support only a finite number of entities, thus limiting expandability. In contrast, each element of the MSB architecture is a completely autonomous entity which, rather than needing to report to an MCPU or other element for interfacing with a network control center (i.e., network management system or NMS), interfaces directly with the NMS. However, this capability limits the size of a network that can be built with MSB switches, because as the network grows, the number of entities communicating with the NMS can overwhelm it. Also, in the MSB architecture, routing complexity grows considerably with each additional node, with concomitant problems in network administration and connection management--e.g., more switches to manage, each generating more network traffic and more network overhead. For these reasons, the MSB architecture is truly acceptable for only relatively simple or small networks.
In the hierarchical architecture, catastrophic failures are caused by common control element failure. Hidden performance limitations also exist in the architecture in that the switching is performed by a level 3 processor, such as the SSU, so that all of the traffic--every single packet through the system--must be deposited into the SSU, and must be processed by the SCPU. Eventually, these common control elements are unable to support any more lines.
Another drawback of the hierarchical architecture is its engineering and configuration complexity. For example, the maximum number of packets which can be processed is somewhat unpredictable, being dependent on the type of traffic driven through level 2 and other considerations. This imposes a significant degree of sophistication on the system, such as merely to determine whether the addition of another level 2 processor will increase total thoughput of the switch (e.g., the system may be level 3 bound, or level 2 bound, depending on the traffic mix).
A further disadvantage of the hierarchical architecture is the relatively high cost of the first port, which makes the architecture less competitive from a cost standpoint for small configurations. All of the common control elements necessary to support a large number of lines (for example, 96) are required even if considerably fewer lines (e.g., three) are being used at a particular site. In contrast, a single element desktop system is available with the MSB architecture for efficient and cost effective handling of up to eight lines, but subject to the MSB disadvantages noted above.
In the hierarchical architecture, one processor card set performs the high speed processing in levels 1 and 2 of the input line. Time intensive processing associated with switching and routing is performed in level 3 of a second processor card, and in levels 1 and 2 of the output line on a third processor card set. Because the traffic must pass through three separate processor card sets, the interprocessor communication requires additional processing overhead.
It is instructive to examine the similarities and differences in connection management in the hierarchical distributed and MSB flat architectures. The data structures used by both architectures for connection management include (i) line control block (LCB), call control block (CCB), and routing table. An LCB, which contains line control information such as line status (available/down), and logical channel number (LCN) availability/assignment, is allocated at initialization time for each transmission line connected to the packet switch. The LCB describes the characteristics of a transmission line and contains the line ID. More importantly, it provides a logic channel map. In packet switched networks, a connection is defined by logical channels. All packets bearing a particular logical channel number are associated with the connection, and that LCN is used to perform routing and switching. If the packet arrives on a certain input line with a particular LCN, it must be transmitted to a specific output line with an identified LCN. This is the nature of the switching process.
A CCB is allocated by level 3 process (processes in MSB architecture) during call establishment, and is deallocated during call clearing. The CCB contains connection control information providing a pointer to the source side LCB and LCN, and a pointer to the destination side LCB and LCN. Here, the terms "source" and "destination" merely identify the direction of the call request packet through the network. In fact, the source and destination sides are symmetrical in that packets from the source side are switched to the destination side, and vice versa, so that for any given packet, either side can be the input side and the opposite side is then the output side. One routing table is loaded into the switch at initialization time, the table containing an entry for each network address. An entry contains one or more lines over which the switch can route calls/packets for the given destination address. These are basic general data structures, and an illustration of their operation in the establishment of a call connection will be described presently.
In the hierarchical architecture, connection management is entirely controlled by the level 3 processor (SCPU) common control element (see FIG. 1). A connection is established when a call request (CR) packet is received, according to the following procedure. A CCB is allocated and linked to the LCB of the input/source line; specifically, to the LCB's logical channel identified in the CR packet header. An output line is then selected by using the called address and the routing table. The selection process calls for checking the line availability and the logical channel availability of each candidate line, to make the "best choice". The CCB is linked to the selected output/destination line LCB (and LCN). The output LCN is then inserted into the CR packet header, and the packet is sent to the mailbox of the level 2 processor which controls the output line (destination side).
The linkage defining this connection is illustrated in FIG. 3. During routing and call setup, the linkage must be established. A CR packet 22 arrives across the source side transmission line associated with LCB 25. The CR packet is received and delivered by levels 1 and 2 processes, which is the extent of their function, and then the level 3 process takes control. Level 3 uses the information obtained from level 2 regarding the line and logical channel on which the packet was received, and performs the appropriate routing using its routing table. The address identifies a user number, which is to be routed to a destination side line in this switch. The routing table identifies that line from the address, and hence, the routing. Level 3 must then look into the LCB 28 of the identified destination side line to ascertain whether the line is both up and available. If both of those conditions are satisfied, level 3 finds an unused LCN and allocates it, by writing into it, indicating that channel is now being used, and allocates a CCB 26 for linking the two LCBs. After being established in this manner between source and destination, the connection enters the "data transfer phase".
For the duration of the call connection in that phase, all data packets received from either direction (source or destination side) are switched to the other side (the output side) using the input line and packet header LCN to trace the linkage to the CCB and output LCB and to replace the input LCN with the output LCN for the next switch to repeat the process.
In the hierarchical architecture illustrated in FIGS. 1 and 2, the connection is established and the switching is performed by a single element, the SCPU, with a consequent major drawback that all connections are vulnerable to a failure of this level 3 processor, with no possibility of establishing new connections. A further disadvantage is that total switch performance is limited by the number of packets the level 3 common control element can process in a given time interval, and since X.25 level 3 processing (by way of example) is about 10 to 20 times less than level 2 processing, then for a given technology the maximum switch size would run approximately twenty fully loaded line cards.
Another significant drawback of the hierarchical scheme is the inefficiency associated with a requirement of repeated copying of each packet from one memory bank to another in each packet switch. In the system of FIG. 1, the incoming packet is first copied into the applicable input LPM level 2 processor 16. Then the LPM copies the same packet into global memory SSU 10, and puts it in a mailbox so that the SCPU level 3 processor 14 can read it and insert the output data structure. Then the SCPU processes the packet, and puts it in the output LPM's mailbox on the SSU. Thereafter, the output LPM must copy the same packet into its local memory for transmission over the output link. Thus, each packet is copied three times in each switch.
In the MSB architecture connection management scheme, the level 1, level 2 and level 3 processing is identical to that of the hierarchical architecture, except for certain aspects described below. However, various inefficiencies are introduced which do not exist for the hierarchical architecture and which severely limit MSB architecture usefulness. In MSB, the routing is typically performed at least twice within the device (box), because each card is an autonomous self-contained switch and an input line and an output line are generally located on separate cards in the device. In theory, switching may be performed an infinite number of times in an MSB architecture, which constitutes a "daisy chain" problem (discussed below).
All the connection management data structures (CCB, LCB, routing table) are kept in local memory on each card. The routing table on each card is unique to that card (i.e., a complete switch), and is very small since the switch system contains only the following lines: (1) local lines on the card; and (ii) trunk lines to each of the other switches (cards) in the box, which constitute virtual lines. As noted above, some implementations of this architecture use cables such as RS232 for interconnection, while other implementations use a shared medium such as a VME bus. In the present specification, trunk lines are defined as lines interconnecting switches internal to the network over which an optimized protocol is often used, whereas DTE lines (data terminal equipment, or subscriber lines), the other line type, are network entry lines over which a slower protocol is used to provide validation, error detection, accounting, and so forth.
The MSB architecture poses a network route generation problem for the NMS because of the sheer volume of routing tables--one for each card at each node. The route generation processing time, computer power requirements and management grows exponentially with growth of the number of switches in the network. Currently, most NMSs are designed to support several dozen to several hundred nodes. By way of example, an NMS capable of supporting up to 1000 switches would be of a size adequate for a global network of hierarchical switches which support ten to twenty line cards each, but even an NMS of that size would be grossly inadequate for an architecture where each card is a separate switch.
Routing of a CR packet is processing intensive. For example, the currently available TP4900 hierarchical architecture packet switch can switch from 10,000 to 15,000 data packets per second, on already-established call connections. However, it can only establish about 250 connections per second, in the absence of switching data packets. Routing may occupy up to 15% of all connection establishment processing, 60% on each transit node for each connection establishment. This disparity between the time and processing required for call connection and data transfer phase switching reflects the fact that the level 3 processor common control element must perform all of the additional processing at call setup.
A corresponding problem is encountered in the MSB architecture because of double routing inefficient real-time processing of subscriber traffic. In any multi-line card architecture, the normal routing case selects an output line which is controlled by a line card other than the input card. In the MSB architecture, where each card acts as a switch, the first card routes to an inter-card trunk line as the output line; the second card routes again, this time to a transmission line to another node in the network. Thus, in this architecture, the costly process of routing is performed at least twice. This is particularly unacceptable in network applications such as transaction processing, e.g., credit card verification or automatic teller banking, where there is no data transfer phase--merely many call setups with instant call clearing. It would therefore be highly desirable to perform routing only once for management of each call connection.
While double call routing is a significant problem which occurs for the normal case, under some less frequent circumstances an even more serious problem may be encountered in the MSB architecture. Specifically, a daisy chain route path may be established which can pass through multiple numbers of cards in the box. When this occurs, all packets of the connection are processed by each card on the daisy chain, resulting in duplicate processing, resource usage, and delay within one node (box). In fact, double routing is simply a special case of daisy chain routing.
As an example, daisy chain routing may occur when an MSB device has no available path to route a call request. When that happens, the affected device clears the pending connection back to the preceding device for that CR. The latter device's destination side card will then route the call over the next best path, which may be via a third card within the MSB device. FIG. 4 illustrates the problem in the MSB architecture. A CR packet is received by card 30, which routes it (as CR #1) over a virtual trunk line across CP (communication processor) bus 33, to card 32. Card 32 performs a second routing (constituting the double call routing problem) and selects a local trunk line, sending the CR out of the device. Subsequently, card 32 receives a Clear Request (CLR) packet back for that CR, because a node downstream (which may be a considerable distance away, geographically) has no path currently available to route this call. Card 32 then attempts to reroute the CR packet (as CR #2) via adjacent card 34, which selects one of its own local trunks to dispatch the CR packet. If a path exists to route the call to the destination, a call accept (CA) packet will be received back from the destination. The CA packet traverses first and second hops via cards 34, 32 and 30. Each hop involves the sending of a packet from one device to a second device over a bus, cable or other interconnection fabric between the two devices. This routing creates the daisy chain problem, because from that point forward, every data packet traversing the established call connection follows that same path through three cards.
The route generation problem is attributable to the existence of too many routing tables in the MSB architecture, where one routing table is provided on and unique to each card. For a robust network, more than one path, and ideally, several paths, should exist between source and destination. In the event that a line fails, the routing tables are structured to route the call through other switches. Such alternative paths may not be the best choice, but it is desirable that the routing tables should have that capability. Each routing table is aware of the status of the connecting lines to its card, but not of the status of the lines in or to other cards in the box. Hence, if a line is down, a packet may be routed in haphazard fashion because the routing table for each card will deal only with the status of lines directly connected to that card. In contrast, no such problem exists in the hierarchical switch architecture, because only one routing entity exists, at level 3, and that entity is aware of the status of all lines in the switch at all times.
Turning now to system administration in a packet switching device, the principal administrative functions are to perform as a network management system (NMS) interface for human operators, uploading of statistics/status/accounting collection, downloading of configuration information, fault detection and recovery, internal control of system configuration and statistics/accounting gathering. If a card fails, the system administration process has the capability to examine a configuration diagram and, from that analysis, make a switch to an appropriate backup card.
The methods of system administration used in the hierarchical and MSB architectures are the same in that every switching entity has one central element or process responsible for system administration. The MSB architecture, with its multiple switching entities, has multiple system administrators, each managing one component (one card). In the hierarchical architecture there is only one switching entity, and thus, each device has one overall system administrator. In the hierarchical architecture of FIG. 1, the system administrator is a common control element, MCPU 13.
An initialization, when the device is powered on, the card (one card in the hierarchical architecture, all cards in the MSB architecture) configured with administration (ADMIN) firmware makes a connection to the NMS to announce its existence and request downloading of initial configuration information. Upon receipt of the configuration information, possibly including a code load, ADMIN installs the software and configuration tables into memory and starts the system. In the case of the hierarchical architecture, this includes installation on other cards. The term "card" as used here is a simplistic reference to a subsystem which may consist of a main card and one or several daughter cards.
During initialization, a bootstrap ADMIN program must place a connection to the NMS to receive the system configuration information, and that program must then start the other cards in the system. In the hierarchical architecture, only the MCPU has the ADMIN software. The MCPU must access the NMS, notify the NMS of the network address of the MCPU, announce the need for software, and request an initial program load. The software is loaded, including executable code, data structures, LCBs, and then the system administrator repeats that process for all of the other cards, and subsequently commands them to start operating. In the MSB architecture, each card's ADMIN process performs this task, but only for its card.
For accounting and statistics reporting, processes in each protocol layer (i.e., levels 1, 2 and 3) send information to ADMIN either as a result of ADMIN polling the processes of each entity, or by simply periodically sending fixed information to ADMIN. ADMIN then places a call to the NMS and uploads the information.
For system reconfiguration, the NMS (human operator or computer) places a connection and sends commands to ADMIN, which interprets them and changes the configuration of the desired entity (e.g., takes a line out of service, changes subscriber line privileges, or other action).
For fault detection, ADMIN periodically sends hello messages to each card, and assumes that the card has failed if it does not respond within a specified period of time. ADMIN can initiate recovery by reconfiguring the system and putting into operation a backup (spare) card in place of the failed card. This involves notification to the spare card as well as broadcasting the change to all other affected cards.
When an entire device fails (i.e., a system or node failure, caused by common control element failure, power outage, or the like) the adjacent devices only detect that the line(s) connecting to the failed device are down, and will respond by notifying the NMS of a line down condition. An NMS may deduce that a node has failed by observing that all adjacent nodes are reporting line down conditions for all lines connected to the device. Because all cards in an MSB architecture are line cards, each of which is a completely autonomous self-contained switch (device), in a network utilizing MSB machines the fault detection and recover of line cards is the same as fault detection and recovery of nodes.
In fault detection and recovery, only the hierarchical system is of significant interest, for reasons noted below. In the limited context of this description the term "fault" means failure of the entire card. In the MSB architecture, there may be no explicit finding that a card has failed. Indeed, the only matter of significance at one card when another card fails is that the line (i.e., dedicated point-to-point physical line, or logical/virtual line over a shared bus) to the failed card (a stand-alone switch) is down and will be unavailable when routing is performed. The solution to card failure in MSB, then, and the implementation of recovery, is substantially the same as for failed devices (hierarchical or MSB) within a network. There is no real-time observation and switchover, which means that recovery will be slow. However, the impact of single card failure is not highly significant, either, because each switch is an autonomous, self-contained entity.
The centralized administration system in the hierarchical architecture is very efficient, but has the drawback that its failure will cause the failure of the entire system. Also, in a hierarchical architecture the administration system typically occupies a slot and requires a dedicated cost. The MSB scheme is more robust, simply because each card has its own administration system, but requires considerable overhead as a consequence of the number of devices communicating with the NMS, since each card establishes its own connections. As a connection is established in MSB architecture, each card performs full routing and allocates/creates a CCB (call connection block) to switch data packets during data transfer. As noted in discussing FIG. 4, processing activity takes place at three separate nodes, which is very time consuming and resource inefficient.
It is a principal object of the present invention to provide a new and improved architecture for packet switched digital communication systems, which overcomes the major limitations of the prior art classical hierarchical architecture and the MSB architecture.
Another broad object is to provide a flat, distributed architecture which enables a packet switch to more efficiently handle connection management and system administration.